package com.mamingchao.foundation.arraysort.buckesort.countsort;

/**
 * 计数排序 稳定算法（定义：原始数组 [{4,5},{4,3},{2,1}] ）
 * 依托 key值升序排序算法执行结果 ——》 [{2,1},{4,5},{4,3}] -> 稳定算法
 * 依托 key值升序排序算法执行结果 ——》 [{2,1},{4,3},{4,5}] -> 非稳定算法
 * 算法稳定不稳定，主要看算法执行后，破坏不破坏 原始数组 已然是排好序、不需要变动的部分
 *
 * 第一层 是原始数组 { 1,2,1,1,0,0,3,2,2,2,3}
 * 第二层 是count数组 { 2，3，4，2}
 * 第三次 是累加数组 {2,5,9,11} -> 从1位置开始，count[i] = count[i] + count[i-1]
 * 第四层 是 倒序遍历原始数组-> 原始数组，从右往左遍历；比如 第一个是3，找累加数组index 是3的位置，附上3的值
 * 然后 原始数组index --，向左遍历下一个，然后累加数组 11 -1；重复这个过程，直到 原始数组遍历完
 *
 *
 * { 1,2,1,1,0,0,3,2,2,2,3}
 *      ||
 *      ||
 *      ||
 *      \/
 *  { 2，3，4，2}
 *      ||
 *      ||
 *      ||
 *      \/
 * {2,5,9,11}
 *      ||
 *      ||
 *      ||
 *      \/
 * {0	0	1	1	1	2	2	2	2	3	3}
 * Created by mamingchao on 2021/6/9.
 */
public class StableCountSort {

    public static void main(String[] args) {

        int[] arr ={ 1,2,1,1,0,0,3,2,2,2,3};
        sort(arr,4);
    }

    /**
     *
     * @param arr 原始数组
     * @param limit 数据 基数值（不重复的数据个数）
     */
    public static void sort(int[] arr,int limit){
        int[] count = new int[limit];

        //第一层 生成count 数组
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]] ++;
        }

        // 第二层 生成累加数组
        for (int i = 1; i < limit; i++) {
            count[i] = count[i] + count[i-1];
        }


        //倒序遍历原始数组
        int[] sortedArr = new int[arr.length];

        for (int i = arr.length-1; i > 0; i--) {
            sortedArr[count[arr[i]]-1] = arr[i];
            count[arr[i]] --;
        }

        printArr(sortedArr);
    }

    private static void printArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }
}
